/*
  wxTriangulator
  Copyright 2008 Boleslaw Kulbabinski

  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include<vector>
#include<algorithm>
#include<set>
#include<stack>
#include<string>

using std::vector;
using std::pair;
using std::make_pair;
using std::sort;
using std::multiset;
using std::min;
using std::max;
using std::stack;
using std::string;
using std::swap;

class TriEdge;
class TriVertex;

typedef vector<TriVertex*>::const_iterator VTV_c_iter;

/*
  utilities
*/
inline long CrossProduct(long &x1, long &y1, long &x2, long &y2, long &x3, long &y3);
long CrossProduct(Point v1, Point v2, Point v3);
long CrossProduct(TriVertex *v1, TriVertex *v2, TriVertex *v3);

/*
  data structure
*/
class TriEdge
{
public:
	TriEdge():on_sweep(false),real_side(true),processed(false){}

	TriVertex *origin;
	TriVertex *helper;

	TriEdge *sibling;
	TriEdge *next;
	TriEdge *prev;

	multiset<TriEdge*>::iterator sweep_pointer;
	bool on_sweep;

	bool real_side; // false means surrounding the "outer" infinite side
	bool processed; // side surrounded by this edge is already processed
};

class TriVertex
{
public:
	int index;
	int type;
	long x;
	long y;

	TriEdge *link;
};

class TriStructure
{
public:
	TriStructure(pair<VP_c_iter, VP_c_iter> init);
	~TriStructure();

	void Init(pair<VP_c_iter, VP_c_iter> init);
	void SortVertices(bool (*)(TriVertex *, TriVertex*));
	void AddEdge(TriVertex* v1, TriVertex *v2);

	pair<VTV_c_iter, VTV_c_iter> GetVertices();

private:
	bool test_clockwise_order(TriVertex *centre, TriVertex *v1, TriVertex *v2, TriVertex *v3);
	bool test_clockwise_order(vector<TriVertex*> *points);

	vector<TriVertex*> v_array;
	vector<TriEdge*> e_array;    // only for deletion
};

/*
  algorithm
*/

class SegmentCompare
{
public:
	bool operator()(TriEdge *A, TriEdge *B);
private:
	Fraction x_coordinate(TriEdge *edge, long Y);
};

bool VertexCompare(TriVertex *A, TriVertex *B);

class TriAlgorithm
{
public:
	static long sweepline_pos;

	TriAlgorithm();
	TriAlgorithm(pair<VP_c_iter, VP_c_iter> init);
	void Init(pair<VP_c_iter, VP_c_iter> init);
	void Run();

	vector<pair<int, int> >* GetOutcome();

private:
	int init_status;
	string init_error;

	bool initial_test();
	bool self_intersections_test();
	bool insert_edge(TriEdge *edge, multiset<TriEdge*, SegmentCompare>& sweepline);
	bool erase_edge(TriEdge *edge, multiset<TriEdge*, SegmentCompare>& sweepline);
	bool check_intersection(TriEdge *A, TriEdge *B);

	void mark_new_edge(TriVertex *v1, TriVertex *v2);
	void add_edge(TriVertex *v1, TriVertex *v2);
	int vertex_type(TriVertex *vertex);
	void divide_into_monotone();
	void triangulate_monotone(TriEdge* boundary);

	TriStructure *polygon;
	unsigned int polygon_size;
	vector<pair<int, int> > *outcome;
	vector<pair<TriVertex*, TriVertex*> > waiting_edges;
};

